package loengud.kymnes;

import java.util.Arrays;

public class Sorting {

	/**
	 * Data to be sorted.
	 */
	public static int data[] = 
		{4, 11, 13, 17, 35, 15, 7, 45, 12, 19, 3, 22};
	
	public static void main(String[] args) {
		System.out.println(Arrays.toString(data));
//		Arrays.sort(data);
//		insertionSort(data);
//		mergeSort(data);
		quickSort(data, 0, data.length - 1);
		System.out.println(Arrays.toString(data));
	} // -main
	
	public static void insertionSort(int[] A) {
				
		for (int sorted = 1; sorted < A.length; sorted++) {
			// item to "insert"
			int temp = A[sorted];
			
			int loc = sorted - 1; // start from the end of the 'sorted' list
			while (loc >= 0 && A[loc] > temp) {
				A[loc + 1] = A[loc];	// bump
				loc--;
			} // -while
			
			// put 'temp' to last vacated place
			A[loc + 1] = temp;
		} // -for
		
	} // -insertionSort

	static void mergeSort(int[] A) {
		if (A.length > 1) {
			// split in two
			int[] first = extract(A, 0, A.length / 2);
			int[] last = extract(A, A.length / 2, A.length);
			
			// sort both
			mergeSort(first);
			mergeSort(last);
			
			// merge
			merge(A, first, last);
		}
	} // -mergeSort
	
	static int[] extract(int[] A, int start, int last) {
		int[] res = new int[last - start];
		for (int i = 0; i < res.length; i++) {
			res[i] = A[start + i];
		}
		return res;
	} // -extract
	
	static void merge(int[] dest, int[] a, int[] b) {
		int i = 0, j = 0;
		
		while (i < a.length && j < b.length) {
			if (a[i] < b[j]) {
				dest[i + j] = a[i];
				++i;
			} else {
				dest[i + j] = b[j];
				++j;
			}
		} // -while
		
		// rest
		for (; i < a.length; i++) dest[i + j] = a[i];
		for (; j < b.length; j++) dest[i + j] = b[j];
		
	} // -merge
	
	static void quickSort(int[] A, int lo, int hi) {
		if (hi <= lo) {
			return;	// done
		} else {
			int pivotPos = quickSortStep(A, lo, hi);
			quickSort(A, lo, pivotPos - 1);
			quickSort(A, pivotPos + 1, hi);	
		}
	} // -quickSort
	
	static int quickSortStep(int[] A, int lo, int hi) {
		// pick pivot
		int pivotVal = A[lo];
		
		while (hi > lo) {	 // util (lo == hi)
			// hi--
			while (hi > lo && A[hi] > pivotVal) hi--;
			if (hi == lo) break;
			
			A[lo] = A[hi];
			lo++;
			
			// lo++
			while (hi > lo && A[lo] < pivotVal) lo++;
			if (hi == lo) break;
			
			A[hi] = A[lo];
			hi--;			
		} // -while
		
		A[lo] = pivotVal;
		return lo; // lo == high
	} // -quickSortStep
}
